package com.example.leetcode.leetcode.hot100;

import com.example.leetcode.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author haitao
 * @date 2021/7/15 9:58 上午
 * 二叉树的广度优先遍历
 */
public class Solution102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return null;
        }

        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> currentNum = Collections.singletonList(root.val);
        lists.add(currentNum);

        List<TreeNode> currentLevel = Collections.singletonList(root);
        while (currentLevel.size() > 0) {
            List<TreeNode> nextLevel = new ArrayList<>();
            currentNum = new ArrayList<>();
            for (TreeNode temp : currentLevel) {
                if (temp.left != null) {
                    nextLevel.add(temp.left);
                    currentNum.add(temp.left.val);
                }
                if (temp.right != null) {
                    nextLevel.add(temp.right);
                    currentNum.add(temp.right.val);
                }
            }
            if (currentNum.size()>0){
                lists.add(currentNum);
            }
            currentLevel = nextLevel;
        }

        return lists;
    }

    public static void main(String[] args) {
        TreeNode root =new TreeNode(1);
        TreeNode rl =new TreeNode(2);
        TreeNode rr =new TreeNode(5);
        root.left = rl;
        root.right = rr;
        TreeNode rll =new TreeNode(3);
        TreeNode rlr =new TreeNode(4);
        rl.left = rll;
        rl.right = rlr;
        TreeNode rrr =new TreeNode(6);
        rr.right = rrr;
        Solution102 solution102 =new Solution102();
        System.out.println(solution102.levelOrder(root));
    }

}
